package org.hhchat.leetcode.dp;

/**
 * Created this one by HMH on 2017/6/1.
 * 每次 猜测的过程： 计算得到cost[i][j]，从i到j区间猜测的最小消耗
 * 1. 选中一个k   ->  代码里使用start
 * 2. 将猜测空间分层两个区域，只需要得到两个区域里面最大的消耗
 * 3. 对所有的k，选择最小的猜测消耗
 * 问题为：最小的{最大消耗}
 */
public class code375 {
    public static class Solution {
        public int getMoneyAmount(int n) {
//            区间i->j的消耗
            int[][] cost = new int[n + 1][n + 1];
            return dp(cost, 1, n);
        }

        //k + dp(i,k-1)+d(k+1,j)
        int dp(int[][] cost,int i, int j) {
            if(i>=j) return 0;
            if(cost[i][j]!=0) return cost[i][j];
            int res=Integer.MAX_VALUE;
            for(int start = i;start<=j;start++)
            {
                int temp = start + Math.max(dp(cost, i, start - 1), dp(cost, start + 1, j));
                res = Math.min(res, temp);
            }
            cost[i][j] = res;
            return res;
        }
    }
    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.getMoneyAmount(10));
    }

}
